class Solution {
    public int majorityElement(int[] nums) {
        int len = nums.length;
        HashMap<Integer,Integer> map = new HashMap<>();
        int sum = 0;
        for(int i = 0;i<len;i++) {
            if(map.containsKey(nums[i])) {
                map.put(nums[i],map.get(nums[i])+1);
            }else {
                map.put(nums[i],1);
            }
        }
        Set<Map.Entry<Integer,Integer>> entryset = map.entrySet();
        int max = 0;
        int ret = 0;
        for(Map.Entry<Integer,Integer> entry : entryset) {
            if(entry.getValue()>max) {
                max = entry.getValue();
                ret = entry.getKey();
            }
        }
        return ret;
    }
    public int majorityElement1(int[] nums) {
        int len = nums.length;
        int candidate = 0;
        int sum = 0;
        for(int i = 0;i<len;i++) {
            //如果票数为0就换候选人
            if(0 == sum) {
                candidate = nums[i];
            }
            if(nums[i] == candidate) {
                sum++;
            }else {
                sum--;
            }
        }
        return candidate;
    }
}